Deflate compression (RFC 1951) is a compression method on which ZLIB (RFC 1950) and GZIP (RFC 1952) are based and uses LZ77 encoding. In the LZ77 encoding, a repeated portion of a character string in data is searched for and the character string is replaced with the position and length of the repeated portion to compress the data. For example, if a character string, “IBM is IBM”, is encoded using the LZ77 encoding, the second occurrence of “IBM” is compressed since that portion is a repeated portion. Specifically, the portion is compressed by replacing it with a code such as “7, 3” which indicates that “a length of three characters that appears seven characters before is repeated”. In this case, the longer the repeated portion, the higher the compression ratio is.
In the specifications for deflate compression, up to 32 KB (kilobytes) of data preceding a character string is searched for a repeated occurrence of that character string, which uses large amounts of processing power for comparing character strings for searching for repeated occurrences of character strings.
Accordingly, handling this processing by software uses a large amount of processing time. Hashing can be used to reduce the search time by software. However, if many character strings have the same hash value, hashing can discard some of the character strings. That is, considering processing time and buffer capacity, it is difficult to find all of the character strings without omission.
In some character string search methods, each of the bits that make up a character is held in a memory cell of a content addressable memory (hereinafter “CAM”). Because these memory cells are more densely packed, the memory cells can be more prone to errors called soft errors due to the influence of cosmic rays or other noise. Some conventional memories have error detection circuits such as parity check circuits in order to improve the reliability. CAMs can be designed to include a parity bit for CAMs to perform parity error detection.
Generally, if an error occurs in a memory cell of a CAM, processing halts at that point in time. To avoid such a halt, it is actually desirable that an error correction circuit such as ECC be incorporated. However, a CAM needs an ECC circuit to be incorporated for each byte, which increases the circuit size too much.